#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict)
    {
        int n = wordDict.size();
        int sz = s.size();
        vector<bool> dp(sz + 1);
        dp[0] = true;

        for (int i = 1; i <= sz; i++)
            for (int j = 0; j < n; j++)
            {
                int tmp = wordDict[j].size();
                if (i >= tmp && s.substr(i - tmp, tmp) == wordDict[j]) dp[i] = dp[i] || dp[i - tmp];
            }

        return dp[sz];
    }
};


class Solution
{
    const int int_max = 0x3f3f3f3f;
public:
    int coinChange(vector<int>& coins, int amount)
    {
        const int N = 1e4 + 2;
        int dp[13][N];
        for (int i = 0; i <= amount; i++)
        {
            dp[0][i] = int_max;
        }
        dp[0][0] = 0;
        int n = coins.size();
        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= amount; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if (j >= coins[i - 1]) dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
            }

        return dp[n][amount] >= int_max ? -1 : dp[n][amount];
    }
};